package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: xiaomi
 * @date: 2021/4/21
 * @description: 91. 解码方法
 * 官方的答案很简洁，可以学习一下。我的方法做了很多的判断
 */
public class B_91_解码方法 {
    static B_91_解码方法 action = new B_91_解码方法();

    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
//        test4();
//        test5();
        test6();
    }

    static void test1() {
        //0
        String s = "000";
        int res = action.numDecodings(s);
        System.out.println("res = " + res);
    }

    static void test2() {
        //2
        String s = "11106";
        int res = action.numDecodings(s);
        System.out.println("res = " + res);
    }

    static void test3() {
        //3
        String s = "226";
        int res = action.numDecodings(s);
        System.out.println("res = " + res);
    }

    static void test4() {
        //1
        String s = "1";
        int res = action.numDecodings(s);
        System.out.println("res = " + res);
    }

    static void test5() {
        //5
        String s = "1123";
        int res = action.numDecodings(s);
        System.out.println("res = " + res);
    }

    static void test6() {
        //
        String s = "301";
        int res = action.numDecodings(s);
        System.out.println("res = " + res);
    }


    /**
     * dp[i] 表示i 时的最大解法
     * 当 chars[i]可以跟 chars[i-1] 合并时，dp[i]=dp[i-1]+1
     *
     * @param s
     * @return
     */
    public int numDecodings(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        if (chars[0] == 48) {
            return 0;
        }
        //pre check 
        for (int i = 1; i < len; i++) {
            if (chars[i] == 48) {
                if (chars[i - 1] > 50 || chars[i - 1] == 48) {
                    return 0;
                }
            }
        }
        if (len < 2) {
            return 1;
        }
        //考虑2位的特殊情况
        if (len == 2) {
            if (chars[1] == 48) {
                if (chars[0] == 49 || chars[0] == 50) {
                    return 1;
                } else {
                    return 0;
                }
            }
            if (check(chars, 0, 1)) {
                return 2;
            } else {
                return 1;
            }
        }
        int index = 2, i = 1;
        int[] dp = new int[len];
        dp[0] = 1;
        for (; index < len; i++, index++) {
            if (chars[index] == 48) {
                //如果后一位数是0，那么 i必须是 1 or 2
                if (!(chars[i] == 49 || chars[i] == 50)) {
                    return 0;
                }
                dp[i] = dp[i - 1];
            } else {
                if (chars[i] == 48) {
                    dp[i] = dp[i - 1];
                } else {
                    if (check(chars, i - 1, i)) {
                        if (i == 1) {
                            dp[i] = dp[i - 1] + 1;
                        } else {
                            dp[i] = dp[i - 1] + dp[i - 2];
                        }

                    } else {
                        dp[i] = dp[i - 1];
                    }
                }
            }
        }
        //判断最后一位
        if (chars[i] == 48) {
            dp[i] = dp[i - 1];
        } else {
            if (check(chars, i - 1, i)) {
                if (i == 1) {
                    dp[i] = dp[i - 1] + 1;
                } else {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[len - 1];
    }

    private boolean check(char[] chars, int lastIndex, int index) {
        if (chars[lastIndex] == 49) {
            return true;
        }
        if (chars[lastIndex] == 50) {
            if (chars[index] > 54) {
                return false;
            } else {
                return true;
            }
        }
        return false;

    }
}
